import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * Created by L.jp
 * Description:有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个
 * 开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重
 * 叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。
 * User: 86189
 * Date: 2021-11-21
 * Time: 15:56
 */
//贪心策略
//1. 每次都选择开始时间最早的活动，不能得到最优解。
//2.每次都选择持续时间最短的活动，不能得到最优解。
// 3. 每次选取结束时间最早的活动，可以得到最优解。按这种方法选择，可以为未安排活动留下尽可能多的时间。
class  myComparator implements Comparator<int[]>{
    @Override
    public int compare(int[] o1, int[] o2) {//结束时间是一个一维数组
        return o1[1]-o2[1];//让结束时间按照递增的顺序
    }
}
public class ActivitySelection {
    public static int maxActivity(int[][]events){
        int num=1;
        int i=0;//第一个活动
        for(int j=1;j< events.length;j++){//从第二个活动开始，第一次先让他跟第一个活动比较时间，如果第二个的开始时间比第一个活动的结束时间大，那么安排在同一天的活动数量就+1,接着去找下一个符合条件的活动
            if(events[j][0]>=events[i][1]){//如果后者的起始时间比上一个活动的结束时间大
                num++;//那么活动数量加1
                i=j;//可以理解为记录上一次的结束时间的下标，以便下一次活动安排的计算
            }
        }
        return num;
    }

    public static void main(String[] args) {
        int number=0;
        System.out.println("请输入活动个数：");
        Scanner scan=new Scanner(System.in);
        number=scan.nextInt();
        int[][] events=new int[number][2];
        System.out.println("请输入活动时间：");
        for(int i=0;i<number;i++){
            events[i][0]=scan.nextInt();
            events[i][1]=scan.nextInt();
        }
        Arrays.sort(events,new myComparator());
        int ret=maxActivity(events);
        System.out.println("最大的活动数量是"+ret);
    }
}
